package Q142;

import java.util.HashSet;
import java.util.Set;

/**
 * 唤醒链表2
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
 *
 * @author 23737
 * @time 2021.11.05
 */
public class Test {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/**
 * hashset 低效
 */
class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pre = head;
        Set<ListNode> set = new HashSet<>();
        while (pre != null) {
            if (set.contains(pre)) return pre;
            set.add(pre);
            pre = pre.next;
        }
        return null;
    }

    /**
     * 快慢指针
     * @param head
     * @return
     */
    public ListNode detectCycle2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}
